package demo.practice.competition;

import java.util.*;

class KV {
    Integer k;
    Integer v;

    public KV(Integer k, Integer v) {
        this.k = k;
        this.v = v;
    }

    public Integer getK() {
        return k;
    }

    public Integer getV() {
        return v;
    }

    @Override
    public String toString() {
        return "KV{" +
                "k=" + k +
                ", v=" + v +
                '}';
    }
}

public class P1000080 {
    public static void main(String[] args) {
        P1000080 p1000080 = new P1000080();
        p1000080.halfQuestions(new int[]{1000,1000});
    }

    public int halfQuestions(int[] questions) {
        int p = questions.length / 2;
        PriorityQueue<KV> priorityQueue = new PriorityQueue<KV>(
                (o1, o2) ->  o2.getV()-o1.getV()
        );
        int[] bucket = new int[1000];
        for (int question : questions) {
            bucket[question-1] += 1;
        }
        for (int i=0;i<bucket.length;i++) {
            if (bucket[i] > 0) {
                priorityQueue.add(new KV(i, bucket[i]));
            }
        }
        int time = 0;
        //Collections.reverse(priorityQueue);
        while (p > 0 && priorityQueue.size() > 0) {
            p = p - priorityQueue.poll().getV();
            time++;
        }
        return time;
    }
}
